package mo.leetcode_top;

import java.util.*;

public class L380_RandomizedSet {

    private List<Integer> nums = new ArrayList<>();
    private Map<Integer, Integer> indices = new HashMap<>();
    private Random random = new Random();


    public L380_RandomizedSet() {

    }

    public boolean insert(int val) {
        if (indices.containsKey(val)) {
            return false;
        }
        int size = nums.size();
        indices.put(val, size);
        nums.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!indices.containsKey(val)) {
            return false;
        }
        Integer index = indices.get(val);
        int last = nums.get(nums.size()-1);
        indices.put(last, index);
        nums.set(index, last);
        nums.remove(nums.size()-1);
        //要在更新索引之前删除，防止重复
        indices.remove(val);
        return true;
    }

    public int getRandom() {
        int i = random.nextInt(nums.size());
        return nums.get(i);
    }

    public static void main(String[] args) {
        L380_RandomizedSet test = new L380_RandomizedSet();
        test.insert(0);
        test.insert(1);
        test.remove(0);
        test.insert(2);
        test.remove(1);
        System.out.println(test.getRandom());
    }
}
